package com.zq.solution.algorithm.divideAndConquer;

import com.zq.solution.treenode.TreeNode;

/**
 * @ClassName CommonAncestor
 * @Description 最近公共祖先
 * @Author ZQ
 * @Date 2020/12/7 15:25
 * @Version 1.0
 */
public class CommonAncestor {
    public TreeNode<Integer> commAncestor(TreeNode<Integer> root ,TreeNode<Integer> node1,TreeNode<Integer> node2){
        //1、root是null,或者只有root一个节点，返回root
        if (root == null) return null;
        if (root == node1 || root == node2) return root;
        TreeNode<Integer> left = commAncestor(root.left,node1,node2);
        TreeNode<Integer> right = commAncestor(root.right,node1,node2);

        //node1 和 node2 都在左边
        if (left != null) return left;
        //node1 和 node2 都在右边
        if (right != null) return right;
        //node1 和 node2 一左一右
        return root;
    }
}
